| class DIGRAPH_ALG{NTP} |
|---|
| **** | The default version of the algorithm class expects node indices of type NTP and will any kind of read-only directed graph. Using this version simplifies some uses but can be significantly less efficient |
| DIGRAPH_ALG{_,_} |
| is_topo_order(g: GTP,nodes: $ARR{NTP}): BOOL .. Included as is_topo_order |
|---|
| **** | Verify that the nodes in "node_order" are in topological order, that each node's order is greater than the order of any of its parents. Better methods probably exist... |
| bf!(once g: GTP,once n: NTP): NTP .. Included as bf! |
|---|
| **** | Return all nodes reachable from "n" in breadth first order With inout arguments, also return the depth of the node |
| df!(once g: GTP,once n: NTP): NTP .. Included as df! |
|---|
| **** | Return all nodes reachable from "n" in depth first order |
| layer!(once g: GTP): SET{NTP} .. Included as layer! |
|---|
| **** | Return the "layers" of the graph, i.e. peel off successive root sets Current indegree holds the current number of incoming per node When the number of incoming goes to zero, the node is visited and the current indegree values of all its outgoing are decremented. All nodes/edges start out live. Loop, at each iteration:
____Find_the_nodes_that_have_no_live_incoming_edges_and__yield_them ____Mark_the_nodes_and_all_edges_going_out_of_them_as_dead Until no more nodes are left alive |
| sink!(once g: GTP): NTP .. Included as sink! |
|---|
| **** | Yield all sink nodes in the graph "g" |
| source!(once g: GTP): NTP .. Included as source! |
|---|
| **** | Yield all source nodes in the graph "g" |
| topo_order!(once g: GTP): NTP .. Included as topo_order! |
|---|
| **** | Yield nodes in topological order |